# 566. 重塑矩阵
# 在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。

# 给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。

# 重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。

# 如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

 

# 示例 1：

# ![img](/Users/apple/Desktop/test/leetcode/assets/reshape1-grid.jpg)

# 输入：mat = [[1,2],[3,4]], r = 1, c = 4
# 输出：[[1,2,3,4]]
# 示例 2：

# ![img](/Users/apple/Desktop/test/leetcode/assets/reshape2-grid.jpg)

# 输入：mat = [[1,2],[3,4]], r = 2, c = 4
# 输出：[[1,2],[3,4]]


# 提示：

# m == mat.length
# n == mat[i].length
# 1 <= m, n <= 100
# -1000 <= mat[i][j] <= 1000
# 1 <= r, c <= 300

# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/reshape-the-matrix
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


from time import time
from typing import List


class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        
        # 解法一, 官解
        m, n = len(mat), len(mat[0])
        if m * n != r * c:
            return mat
        
        ans = [[0] * c for _ in range(r)]
        for x in range(m * n):
            ans[x // c][x % c] = mat[x // n][x % n]
        
        return ans
        
        # 解法2
        if len(mat)*len(mat[0]) == r*c:
            _mat = [[]]
            l = 0
            k = 0
            for i in range(len(mat)):
                for j in range(len(mat[0])):
                    if len(_mat[k]) == c:
                        k +=1
                        _mat.append([])
                    _mat[k].append(mat[i][j])
            return _mat
        else:
            return mat
    
    
if __name__ == '__main__':
    start = time()
    a = Solution()
    print(a.matrixReshape(mat = [[1,2],[3,4]], r = 1, c = 4))
    print(a.matrixReshape(mat = [[1,2],[3,4]], r = 2, c = 4))
    print(a.matrixReshape(mat = [[1,2],[3,4]], r = 4, c = 1))
    end = time()
    print('='*40)
    print("start time is ", start*1000)
    print("end   time is ", end*1000)
    print("耗时:",end*1000 - start*1000,"ms")